FIGS. 3A-3C provide an example of a version of software in three different formats. For example, FIG. 3A illustrates the source code version of the software as written by a programmer in the BASIC programming language. The program prints the word “world” twice, each followed by an instruction to move to a new line. FIG. 3B illustrates the same version in a compiled, assembly language code format using the instructions set for the popular Motorola 6809 processor; the processor uses numbers to identify the operations it will perform and the assembly language version show what those operations are (e.g., the byte “8e” is a number value that instructs the processor to load a value in the X register (“LDX”)). Finally, FIG. 3C illustrates the same base version in a compiled, machine language code format that is suitable for execution by the 6809 processor. In other words, a programmer may write in the software in source code. The source code is later “compiled” into machine code, e.g., a collection of values whose operation is somewhat difficult for humans to decipher. Assembly language makes it easier for humans to ascertain the functions of the machine code (software may also be written in assembly language).
Many software providers routinely update their software, making changes that may range from relatively minor to dramatically different. In that regard, FIGS. 4A-4C illustrate the corresponding formats for an updated version of the software shown in FIGS. 3A-3C. For example, FIG. 4A illustrates how a programmer may have updated the source code version of the software shown in FIG. 3A. The updated version contains instructions to print the word “hi” followed by an instruction to move to a new line, and to thereafter print the word “world” followed by a move to another new line.
In other words, the only difference between the updated version of the software (FIG. 4A) and the prior version of the software (FIG. 3A) (hereafter, the “base” software) is that the source code of the updated version prints the word “hi” instead of the first instance of printing the word “world”.
Many software providers do not resend the entire new version of a program to their end users. One typical reason is that the programmers may have relatively minor changes to an otherwise large program. Accordingly, rather than sending an entirely new version to their end users, the provider may send a patch instead. A patch is typically a small program that represents the differences between the base and updated versions as well as instructions for making the changes. (A patch may also include only the changes if a program for installing the changes is already available on the end user's computer.) When executed by the end user's computer, the patch modifies the machine code of the base version so that it matches the updated version.
However, FIG. 5 illustrates that even a minor update of the base version software that simply replaces a single occurrence of the word “world” with the word “hi”, results in numerous differences throughout the corresponding machine code formats. For example, FIG. 5 shows a part 52 of the base version in machine code format (from FIG. 3C) and a part 54 of the corresponding updated version of the software (from FIG. 4C). As can be seen by the circled portions, the updated version shows numerous bytes that are either different from or not included in the base version.
Thus, generating a patch for creating the updated version of the software in the machine code format from the corresponding base version would result in a patch that is relatively large.
The size and efficiency of patches can be important considerations with respect to patches. For example, if a patch is sent over a network, such as the Internet or a cell phone network, the speed of the network may delay the delivery of a large patch. Moreover, some devices such as cell phones may have a relatively small amount of memory, which can also militate in favor of keeping patches small.